import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
enum 	MutationType{RM,EM}; // Random, Exchange, Displacement, Scramble, Insertion, Inversion, Displaced Inversion mutation operators
enum	CrossoverType{OPX, TPX, UX}; // One-Point, Two-Point, Uniform, Half Uniform crossover operatorS
enum	ScaleType{NONE, RANK, SIGMA, BOLTZMANN}; // No scaling, Rank, Sigma, Boltzmann
enum	SelectionType{RWS, TS, ATS}; // Roulette Wheel, Tournament, Alternate Tournament

public class Genetic {
	///////////////////////////////////////////////////////////////
	// Private Variable Declarations //////////////////////////////
	///////////////////////////////////////////////////////////////
	Genetic(double crossoverRate, double mutationRate, int populationSize, int chromosomeLength, int mazeRows, int mazeColumns){
		this.crossoverRate		= crossoverRate;
		this.mutationRate		= mutationRate;
		this.populationSize	= populationSize;
		this.chromosomeLength	= chromosomeLength;
	
		bestPath = new int [mazeRows][mazeColumns];
		memory = new int [mazeRows][ mazeColumns];
		chrs =  new ArrayList<Chromosome>();// population of chromosomes
		this.xtype = CrossoverType.TPX;
		this.mutType= MutationType.EM;
		this.selType = SelectionType.ATS;
		this.scType = ScaleType.RANK;
		CreateStartPopulation();
		//System.out.println(System.getProperty("user.dir"));
		
		try {
			writer = new FileWriter(sFileName);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	// used in Boltzmann selection
	static final double BOLTZMANN_MIN_TEMP=1;
	static final double BOLTZMANN_DT= 0.05;
	FileWriter writer;
	ArrayList<Chromosome> chrs; 
	int populationSize;		// size of population
	int generation = 1;			// current generation
	MutationType mutType;
	CrossoverType xtype;
	ScaleType scType;
	SelectionType selType;
	int beg, end;
	String curDir = System.getProperty("user.dir");
	String sFileName = "C:\\TEMP\\genetic.csv";
	
	// genetic algorithm setting variables
	double crossoverRate;	// probability of a crossover being performed when creating offspring
	double mutationRate;	// probability of a mutation being performed on an offspring
	int chromosomeLength;	// number of genes per chromosome
	int fittestGenomeIndex;	// index of the fittest chromosome in the current population, genomes
	
	// if using SIGMA fitness scaling this holds sigma value for current generation
	// if sigma equals zero, population are identical so the run is halted b/c no solution will be found
	double sigma = 1;
	double boltzmannTemp = populationSize * 2;	// current boltzmann temperature
	
	// track statistical fitness values for the most recent generation
	double averageFitness=0;	// average fitness score
	double	dx = Math.pow((Maze.getWidth() - 0), 2.00);
	double	dy = Math.pow((Maze.getHeight() - 0), 2.00);
	
	double worst = Math.sqrt(dx+dy); //distance from goal
	double bestFitness=worst;		// best fitness score 
	double worstFitness=worst;	// worst fitness score
	double totalFitness=0;	// sum of all fitness scores
	
	boolean busy=false;	// true if the algorithm is in progress, false if paused or population has converged
	boolean sorted=false;// true if the genomes have been sorted by fitness for this generation (to save unnecessary sorting)
	boolean solutionFound=false;			// if true, a solution has been found
	boolean populationConverged=false;	// if true, then population has identical fitness scores, and no solution can be found (ie: local minima)
	
	// need some variables for handling elitism
	boolean useElitism = true;
	int elitismNumBest=1;
	int elitismNumCopies=2;

	// keeps track of what member of the population should currently be evaluated between calls to Epoch()
	// this way the app won't pause while the entire Epoch runs!!  It will only do a small part each time it's called
	int curMemberEvaluated=0;
	
	int [][] memory;
	int [][] bestPath;
	
	
	///////////////////////////////////////////////////////////////
	// Private Member Function Declarations ///////////////////////
	///////////////////////////////////////////////////////////////
	
	void Reset(){	 // reset only a few variables, used when starting a new generation
		totalFitness	= 0;
		double	dx = Math.pow((Maze.getWidth() - 0), 2.00);
		double	dy = Math.pow((Maze.getHeight() - 0), 2.00);
		
		double worst = Math.sqrt(dx+dy); //distance from goal
		bestFitness		= worst;
		worstFitness	= worst;
		averageFitness	= worst;
		sorted			= false;
		sigma			= 1;	
	}
	
	// calculate the fitness scores of some members of the population
	void UpdateFitnessScores(){
		// if starting a new run-through of a population, reset the data
			if (curMemberEvaluated == 0) {
				double	dx = Math.pow((Maze.getWidth() - 0), 2.00);
				double	dy = Math.pow((Maze.getHeight() - 0), 2.00);
				
				double worst = Math.sqrt(dx+dy); //distance from goal
				fittestGenomeIndex		= 0;
				bestFitness		= worst;
				worstFitness	= worst;
				totalFitness	= 0;
				memory = new int [Maze.getHeight()][Maze.getWidth()];
			}

			// update the fitness scores of some chromosomes, keep track of the fittest so far
			while (curMemberEvaluated < populationSize /*&& numPops < 1*/) {
	
				for (int i=0; i<memory.length; i++) {
					for (int j=0; j<memory.length; j++) {
						memory[i][j] = 0;
					}
				}
				
	
				int [] path = new int[chrs.get(curMemberEvaluated).chromozome.length]; 
				path =	chrs.get(curMemberEvaluated).chromozome;
	
				// get the fitness score for this genome
				chrs.get(curMemberEvaluated).dFitness= Maze.testRoute(path, memory,chrs.get(curMemberEvaluated).chromozome );
				
				// if this is the first genome, set the worst fitness score to its fitness, and then
				// compare the worst to every other genome that gets processed
				if (curMemberEvaluated == 0) {
					worstFitness = chrs.get(0).dFitness;
				}
	
				// update total fitness score
				totalFitness += chrs.get(curMemberEvaluated).dFitness;
	
				// if this is the fittest genome so far, store it as fittest
				if (chrs.get(curMemberEvaluated).dFitness < bestFitness)
				{
					bestFitness = chrs.get(curMemberEvaluated).dFitness;
					fittestGenomeIndex = curMemberEvaluated;
					bestPath = memory;
					// check if found the exit
					if (chrs.get(curMemberEvaluated).dFitness == 1.4142135623730951){
						// stop this run, since exit was found
						busy = false;
						solutionFound = true;
						return;
					}
				}else { // check if this genome's fitness score is worse than the current worst
					if (chrs.get(curMemberEvaluated).dFitness > worstFitness) {
						worstFitness = chrs.get(curMemberEvaluated).dFitness;
					}
				}
	
				curMemberEvaluated++;
				//numPops++;
	
			} // next genome
			//System.out.println("Fittest chromosome has "+chrs.get(fittestGenomeIndex).dFitness);
	}
	
	// cross over 2 genomes to make 2 babies
	void Crossover(int [] mom, int [] dad, int[] baby1, int [] baby2){
		// depending on crossover rate (or if both parents are identical) just return parents as is
		if ((Rand.r.nextFloat() > crossoverRate) || (mom == dad)) {

			baby1 = mom;
			baby2 = dad;

			return;
		}
		switch(xtype) {

			case OPX:
	
				CrossoverOPX(mom, dad, baby1, baby2);
	
				break;
	
			case TPX:
	
				CrossoverTPX(mom, dad, baby1, baby2);
	
				break;
	
			case UX:
	
				CrossoverUX(mom, dad, baby1, baby2);
	
				break;
				
			default: break;
	
		} //end switch	
		

		
	}
	
	void CrossoverOPX(int [] mom, int [] dad, int[] baby1, int [] baby2) //one point x-over
	{

		// determine a crossover point
		int cp = Rand.r.nextInt(chromosomeLength - 1); //Int(0, chromosomeLength - 1);

		// copy first cp genes as is
		for (int i=0; i<cp; ++i)
		{
			baby1[i]=mom[i];
			baby2[i]=dad[i];
		}

		// now swap mum and dad contributing genes (ie: crossover)
		for (int i=cp; i<mom.length; ++i)
		{
			baby1[i]=dad[i];
			baby2[i]=mom[i];
		}

	}
	
	void CrossoverTPX(int [] mom, int [] dad, int[] baby1, int [] baby2){//two point
		// determine two crossover points
		int cp1 = Rand.randomInt(chromosomeLength-1); //
		int cp2 = Rand.randomInt(chromosomeLength-1);

		// make sure that cp1 and cp2 aren't equal
		while (cp1 == cp2) {
			cp2 = Rand.randomInt(chromosomeLength-1);
		}

		// make sure cp1 is less than cp2
		if (cp1 > cp2) {
			int temp = cp1;
			cp1 = cp2;
			cp2 = temp;
		}

		// copy first cp1 bits as is
		for (int i=0; i<cp1; ++i)
		{
			baby1[i] = mom[i];
			baby2[i] = dad[i];
		}

		// now swap mum and dad contributing bits (ie: crossover) from cp1 to cp2
		for (int i=cp1; i<cp2; ++i)
		{
			baby1[i]=dad[i];
			baby2[i]=mom[i];
		}

		// copy bits from cp2 up to mum.size as is
		for (int i=cp2; i<mom.length; ++i)
		{
			baby1[i]=mom[i];
			baby2[i]=dad[i];
		}	
	}
	
	void CrossoverUX(int [] mom, int [] dad, int[] baby1, int [] baby2){//uniform x-over
		int [] swapBits = new int [chromosomeLength];

		// probability that a certain bit will be marked for crossover
		// generally 0.5 is used as a reasonable probability
		float crossoverProbability = 0.5f;

		// generate the crossover bit mask (if see a 1, those bits from parents will be crossed over,
		// otherwise (if see a 0) they will be directly transferred to child)
		for (int i=0; i<mom.length; ++i) {

			if (Rand.r.nextFloat() < crossoverProbability) { // mark this bit for crossover, ie: bit = 1
				swapBits[i]=1;
			} else {
				swapBits[i]=0;
			}

		}

		// copy bits from parents to children, following crossover bit mask
		for (int i=0; i<mom.length; ++i)
		{
			if (swapBits[i] == 0) { // copy bit from parents to children as-is
				baby1[i]=mom[i];
				baby2[i]=dad[i];
			} else { // crossover bit from parents to children
				baby1[i]=dad[i];
				baby2[i]=mom[i];		
			}

		}
	}
	
	void CrossoverHUX(int [] mom, int [] dad, int[] baby1, int [] baby2){//half-uniform
		
	}
	
	// mutate a chromosome
	void Mutate(int[]chromozome){
		switch(mutType) {

		case RM:
			MutateRM(chromozome);
			break;
		case EM:
			MutateEM(chromozome);
			break;
		default: break;

		} //end switch	
	}
	
	void MutateRM(int[]chromozome){
		// randomly flip bits based on mutationRate
	
			for (int curBit=0; curBit<chromozome.length; curBit++) {
	
				// should we flip this bit?
				if (Rand.r.nextFloat() < mutationRate)
				{
					// mutate gene randomly
					chromozome[curBit] = Rand.randomInt(4)+1;
				}
	
			}
	}
	void MutateEM(int[]chromozome){//exchange mutation
		// choose two random genes and swap their position

		if (Rand.r.nextFloat() > mutationRate) return;

		//choose first gene
		int pos1 = Rand.randomInt(chromozome.length-1);

		//choose second
		int pos2 = pos1;

		while (pos1 == pos2)
		{
			pos2 = Rand.randomInt(chromozome.length-1);
		}

		//swap their positions
		int temp = chromozome[pos1];
		chromozome[pos1]=chromozome[pos2];
		chromozome[pos2] = temp;
	}
	
	
	// different Selection techniques - can be selected by user
	
	Chromosome Select(){ //select selection scheme
		// perform selection based on type
		switch(selType) {

			case RWS:

				return SelectRWS();

			case TS:

				return SelectTS();

			case ATS:

				return SelectATS();

		default: break;

		} //end switch
		return null;
	}
	
	Chromosome SelectTS(){ //tournament selection scheme
		// randomly select n genomes from the population, and then choose the fittest

		double bestFitnessSoFar = 0;
	  
		int chosenOne = 0;

		// set number of genomes to randomly set to populationSize/20, roughly 5% of the population
		int n = populationSize/20;

		// select n members from the population at random testing against the best found so far
		for (int i=0; i<n; ++i) {

			int thisTry = Rand.randomInt(populationSize-1);

			if (chrs.get(thisTry).dFitness > bestFitnessSoFar) {

			  chosenOne = thisTry;
			  bestFitnessSoFar = chrs.get(thisTry).dFitness;

			}

		}

		// return the champion
		return chrs.get(chosenOne);
	}
	
	Chromosome SelectATS(){ //alternate tournament selection
		// randomly select 2 genomes from the population, and then choose the fittest with
		// probability p, choose least fit with probability 1-p, generally p chosen to be around 0.75

		// allocate two indexes into the population
		int g1 = Rand.randomInt(chrs.size()-1);
		int g2 = Rand.randomInt(chrs.size()-1);

		// make sure they are different
		while(g1 == g2) {
			g2 = Rand.randomInt(chrs.size()-1);
		}

		float probability = 0.75f;

		// now return the chosen individual based on probability
		if (Rand.r.nextFloat() < probability) {
			// return the fitter of the two
			if (chrs.get(g1).dFitness > chrs.get(g2).dFitness) {
				return chrs.get(g1);
			} else {
				return chrs.get(g2);
			}
		} else {
			//return the weaker
			if (chrs.get(g1).dFitness < chrs.get(g2).dFitness) {
				return chrs.get(g1);
			} else {
				return chrs.get(g2);
			}
		}
	}

	
	// Roulette Wheel Selection
	Chromosome SelectRWS(){
		// the higher the fitness score, the more likely that a genome will be selected (but no 
			// guarantee that the best performers will be carried forward to the next generation)
	
			double fSlice = Rand.r.nextFloat() * totalFitness;
	
			double cfTotal = 0.0;
	
			int selectedGenome = 0;
	
			for (int i = 0; i < populationSize; ++i) {
	
				cfTotal += chrs.get(i).dFitness;
	
				if (cfTotal > fSlice) {
					selectedGenome = i;
					break;
				}
	
			}
	
			return chrs.get(selectedGenome);
	}
	
	// scale the fitness scores of the population
	void ScaleFitness(){
		switch(scType)
		{
			case NONE:

				break;

			case SIGMA:

				ScaleSigma(chrs);

				break;

			case BOLTZMANN:

				ScaleBoltzmann(chrs);

				break;

			case RANK:

				ScaleRank(chrs);

				break;
		}
	}
	// different Scaling techniques - can be selected by user
	// Rank Scaling
	void ScaleRank(ArrayList<Chromosome> pop){
		if(!sorted){
			Collections.sort(chrs, new Comparator<Chromosome> (){
				@Override
				public int compare(Chromosome arg0, Chromosome arg1) {
					// TODO Auto-generated method stub
					return (int) (arg0.dFitness-arg1.dFitness);
				}
			});
			sorted = true;
		}
		// now assign fitness according to the genome's position on this new fitness 'ladder'
		for (int i=0; i<pop.size(); i++) {
			pop.get(i).dFitness = i;
		}

		// recalculate values used in selection
		CalculateBestWorstAvTot();
	}
	
	void ScaleSigma(ArrayList<Chromosome> pop){
		double runningTotal = 0;

		// first iterate through the population to calculate the standard deviation
		for (int gen=0; gen < pop.size(); ++gen) {
			runningTotal += (pop.get(gen).dFitness - averageFitness) *
							(pop.get(gen).dFitness - averageFitness);
		}

		double variance = runningTotal/(double)populationSize;

		// standard deviation is the square root of the variance
		sigma = Math.sqrt(variance);

		// now iterate through the population to reassign the fitness scores
		for (int gen=0; gen < pop.size(); ++gen) {
			double oldFitness = pop.get(gen).dFitness;
			pop.get(gen).dFitness = (oldFitness - averageFitness) / (2 * sigma);
		}

		// recalculate values used in selection
		CalculateBestWorstAvTot();
	}
	// Boltzmann Scaling
	void ScaleBoltzmann(ArrayList<Chromosome> pop){
		// reduce the temp a little each generation
		boltzmannTemp -= BOLTZMANN_DT;

		// make sure it doesn't fall below minimum value
		if (boltzmannTemp < BOLTZMANN_MIN_TEMP) 
			boltzmannTemp = BOLTZMANN_MIN_TEMP;

		// iterate through the population to find the average e^(fitness/temp)
		// keep a record of e^(fitness/temp) for each individual,
		// will be used to calculate new fitness for each genome
		double [] expBoltz = new double [chromosomeLength];//vector<double> expBoltz; 
		double average = 0.0;
		
		for (int gen=0; gen < pop.size(); ++gen) {
			expBoltz[gen]=Math.exp(pop.get(gen).dFitness / boltzmannTemp);
			average += expBoltz[gen];
		}

		average /= (double)populationSize;

		// now iterate once more to calculate the new expected values
		for (int gen=0; gen < pop.size(); ++gen) {
			pop.get(gen).dFitness = expBoltz[gen]/average;
		}

		// recalculate values used in selection
		CalculateBestWorstAvTot();
	}
	
	// helper functions for the genetic algorithm
	// calculate the fittest and weakest genome, as well as the average and total fitness scores
	void CalculateBestWorstAvTot(){
		totalFitness = 0;
		double	dx = Math.pow((Maze.getWidth() - 0), 2.00);
		double	dy = Math.pow((Maze.getHeight() - 0), 2.00);
		
		double worst = Math.sqrt(dx+dy); //distance from goal
		double highestSoFar = worst;
		double lowestSoFar  = worst;
		
		for (int i=0; i<populationSize; ++i) {

			// update fittest if necessary
			if (chrs.get(i).dFitness < highestSoFar) {

				highestSoFar = chrs.get(i).dFitness;
				
				fittestGenomeIndex = i;

				bestFitness	 = highestSoFar;

			}
			
			// update worst if necessary
			if (chrs.get(i).dFitness > lowestSoFar) {

				lowestSoFar = chrs.get(i).dFitness;
				
				worstFitness = lowestSoFar;

			}
			
			totalFitness += chrs.get(i).dFitness;
			
			
		} // next chromosome
		
		averageFitness = totalFitness / populationSize;

		// if all the fitnesses are identical then the population has converged
		// so we should stop the run because nothing will ever change now
		if (highestSoFar == worstFitness) {
			sigma = 0;
		}
	}
	// choose a section of a chromosome, sets the beg and end variables to begin and end index of the chosen section
	void ChooseSection(int beg, int end, int max_span, int min_span){
		beg = Rand.randomInt(max_span-min_span);
		
		end = beg;
		
		// find an end
		while (end <= beg) {
			end = Rand.randomInt(max_span);
		}
		this.beg = beg;
		this.end = end;
	}
	
	// create a starting population of genomes, randomly assigned values for each chromosome
	void CreateStartPopulation(){
		for(int i=0;i<populationSize;i++){
			chrs.add(new Chromosome(chromosomeLength));
			//System.out.println(Arrays.toString(chrs.get(i).chromozome));
		}
	}
	
	
	// methods to set operators and genetic functions
	void SetElitism(boolean turnOn, int nBest, int nCopies){
		useElitism = turnOn;
		elitismNumBest = nBest;
		elitismNumCopies = nCopies;
	}
	void SetCrossoverType(CrossoverType newType){
		xtype = newType;
	}
	void SetMutationType(MutationType newType){
		mutType = newType;
	}
	void SetSelectionType(SelectionType newType){
		selType = newType;
	}
	void SetScalingType(ScaleType newType){
		scType = newType;
	}
	
	void Run(){
		busy = true;
	}
	@SuppressWarnings({ "unchecked", "rawtypes" })
	void Epoch(){
		// if still have more work to do, call UpdateFitnessScores to evaluate some more members of the current population
			// will only evaluate as many as have time for (time set and tracked in the UpdateFitnessScores() function
			if (curMemberEvaluated < populationSize) {
				// run some genomes through the maze, see if any make it to the exit!
				UpdateFitnessScores();
				if(solutionFound){
					try {
						writer.append(Integer.toString(generation));
						writer.append(',');
						writer.append(Double.toString(bestFitness));
						writer.append('\n');
						writer.flush();
						writer.close();
					} catch (IOException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				}
			}
			//if(generation % 0 == 0){
				try{
					//FileWriter writer = new FileWriter(sFileName);
					String num = Integer.toString(generation);
					writer.append(num);
					writer.append(',');
					writer.append(Double.toString(bestFitness));
					writer.append('\n');
					writer.flush();
					//writer.close();
				}
				catch(IOException e){
					//e.printStackTrace();
				}
			//}
			//System.out.println("(Genetic call)Best fitness for Gen "+generation + "is " +bestFitness );
			// if done evaluating the current population, create a new population of babies
			if (curMemberEvaluated >= populationSize && !solutionFound) {
	
				// calculate values used in selection
				CalculateBestWorstAvTot();
	
				sorted = false;
	
				ScaleFitness();
				
				// if sigma is zero (either set in sigma scaling or in CalculateBestWorstAv
				// then the population are identical and we should stop the run
				if (sigma == 0) { // ie: sigma close enough to zero, we've converged
					busy = false;
					populationConverged = true;
					return;
				}
	
				// create storage for the baby genomes
				ArrayList<Chromosome> babies = new ArrayList<Chromosome>();
				
				//elitism..TO DO NEED SORT FUNCTION
				if(useElitism){
					// now add a few copies of the best performer from the last generation (ie: elitism)
					// first we need to sort our genomes
					if(!sorted){
						Collections.sort(chrs, new Comparator (){
							public int compare(Object o1, Object o2){
								Chromosome c1 = (Chromosome) o1;
								Chromosome c2 = (Chromosome) o2;
								return (int) (c1.dFitness-c2.dFitness);
							}
						});
						sorted = true;
					}
		
					// now add the required amount of copies of the elitismNumBest most fit genomes to the vecBabyGenomes
					// make sure it's an even number (as babies are added in pairs!!)
					int numBest = elitismNumBest;
					
					while (numBest-- > 0) {
		
						for (int i=0; i<elitismNumCopies; ++i) {
							babies.add(chrs.get((populationSize - 1) - numBest));
						}
		
					}
				}
	
				
	
				// now create a new population
				int	newBabies = 0;// babies.size();
	
	
				while (newBabies < populationSize){
					// select 2 parents
					Chromosome mum = Select();
					Chromosome dad = Select();
	
					// crossover
					Chromosome baby1 = new Chromosome(chromosomeLength);
					Chromosome baby2 = new Chromosome(chromosomeLength);
					Crossover(mum.chromozome, dad.chromozome, baby1.chromozome, baby2.chromozome);
	
					// mutate
					Mutate(baby1.chromozome);
					Mutate(baby2.chromozome);
	
					// add babies to new population
					babies.add(baby1);
					babies.add(baby2);
	
					newBabies += 2;
				}	
				// copy babies back into starter population
				chrs = babies;
				
				// increment generation counter
				generation += 1;		
	
				// start evaluating the new population at the first member
				curMemberEvaluated = 0;
	
				// reset variables before starting calculations on a new generation
				Reset();
	
			}
	}
	void Stop()		 { busy = false; }
		
	// accessor methods
	
	public int [][]		GetBestPath()				{ return bestPath; }
	public int			Generation()				{ return generation; }
	public int			GetFittest()				{ return fittestGenomeIndex; }
	public int			GetPopulationSize()			{ return populationSize; }
	public int			GetCurrentMemberEvaluated() { return curMemberEvaluated; }
	public boolean		Started()					{ return busy; }
	public boolean		SolutionFound()				{ return solutionFound; }
	public boolean		GetPopConverged()			{ return populationConverged; }

}
